Coloration d'un graphe (d'après BAC ES, métropole 2003)

Un petit complément sur les colorations de graphes

On définit le nombre chromatique  \(χ(G)\)  d'un graphe \(G\) , comme étant le nombre minimal de couleurs à utiliser pour colorier les sommets d'un graphe sans que deux sommets adjacents soient de la même couleur.

Par exemple, pour le graphe ci-dessous, le nombre chromatique est 2.

Remarquons que le nombre chromatique d'un graphe est toujours inférieur ou égal à  \(Δ(G)+1\) , où  \(Δ(G)\)  est le plus grand degré d'un des sommets du graphe  \(G\) .

Par ailleurs, pour un graphe complet  \(K_n\) , on a  \(χ(K_n)=n=Δ(K_n)+1\) .

Énoncé

Un concert de solidarité est organisé dans une grande salle de spectacle. À ce concert sont conviés sept artistes de renommée internationale : Luther Allunison (A), John Biaise (B), Phil Colline (C), Bob Ditlâne, Jimi Endisque (E), Robert Fripe (F) et Rory Garaguerre (G).

Les différents musiciens invités refusant de jouer avec certains autres, l'organisateur du concert doit prévoir plusieurs parties de spectacle. Les arêtes du graphe  \(G\)  ci-dessous indiquent quels sont les musiciens qui refusent de jouer entre eux.

1. Déterminer la matrice d'adjacence du graphe  \(G\)

2. On considère le sous graphe \(G'\)  de  \(G\) , constitué des sommets A, E, F et G.
    a. Que peut-on dire de  \(G'\) ?
    b. En déduire son nombre chromatique  \(χ(G')\) .
    c. Que peut-on en déduire pour  \(χ(G)\)  ?

3. Quel est le sommet de plus haut degré de  \(G\)  ? En déduire un encadrement de  \(χ(G)\) .

4. Après avoir classé les sommets de  \(G\)  par ordre de degré décroissant, colorier le graphe  \(G\) .

5. Combien de parties l'organisateur du concert doit-il prévoir ? Proposer une répartition des musiciens pour chacune de ces parties.